import java.util.*;

public class J1001 {
    static Comparator<Map.Entry<String, Integer>> newComparator = (Map.Entry<String, Integer> entry1,
              Map.Entry<String, Integer> entry2) -> (Objects.equals(entry1.getValue(), entry2.getValue()) ?
            entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue());

    public static List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> hashMap = new HashMap<>();
        for(String word : words){
            hashMap.put(word, hashMap.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(newComparator);
        for(Map.Entry<String, Integer> entry : hashMap.entrySet()){
            pq.offer(entry);
            if(pq.size() > k){
                pq.poll();
            }
        }
        List<String> list = new LinkedList<>();
        while(! pq.isEmpty()){
            list.add(pq.poll().getKey());
        }
        return list;
    }

    public static void main(String[] args) {
//        String[] nums = new String[]{"a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b","b"};
        String[] nums = new String[]{"i","love","leetcode","i","love","coding"};
        System.out.println(topKFrequent(nums, 2));
    }
}
